Symmetric Gauss-Seidel Technique Based Alternating Direction Methods of Multipliers for Transform Invariant Low-Rank Textures Problem

摘要

Transform Invariant Low-Rank Textures, referred to as TILT, can accuratelyand robustly extract textural or geometric information in a 3D fromuser-specified windows in 2D in spite of significant corruptions and warping.It was discovered that the task can be characterized, both theoretically andnumerically, by solving a sequence of matrix nuclear-norm and $\ell_1$-norminvolved convex minimization problems. For solving this problem, the directextension of Alternating Direction Method of Multipliers (ADMM) in an usualGauss-Seidel manner often performs numerically well in practice but there is notheoretical guarantee on its convergence. In this paper, we resolve thisdilemma by using the novel symmetric Gauss-Seidel (sGS) based ADMM developed byLi, Sun \& Toh (Math. Prog. 2016). The sGS-ADMM is guaranteed to converge andwe shall demonstrate in this paper that it is also practically efficient thanthe directly extended ADMM. When the sGS technique is applied to thisparticular problem, we show that only one variable needs to be re-updated, andthis updating hardly imposes any excessive computational cost. The sGSdecomposition theorem of Li, Sun \& Toh (arXiv: 1703.06629) establishes theequivalent between sGS-ADMM and the classical ADMM with an additionalsemi-proximal term, so the convergence result is followed directly. Extensiveexperiments illustrate that the sGS-ADMM and its generalized variant havesuperior numerical efficiency over the directly extended ADMM.